Conclusion

The Fundamental Theorem of Statistical Learning

Let $H$ be a hypothesis class of functions from a domain $X$ to $\{0, 1\}$ and let the loss function be the 0-1 loss. Then, the following are equivalent:

1. $H$ has the uniform convergence property.
2. Any ERM rule is a successful agnostic PAC learner for $H$.
3. $H$ is agnostic PAC learnable.
4. $H$ is PAC learnable.
5. Any ERM rule is a successful PAC learner $H$.
6. H has a finite VC-dimension.